
function wordBreak(s: string, wordDict: Set<string>): boolean {
    var cache = new Map<string, boolean>();    
    function loop(s: string) {
        if (cache.has(s)) return cache.get(s);
        if (wordDict.has(s)) return true;
        else if (s.length > 1) {
            for(var i = 1; i < s.length; i++) {
                if ( loop( s.substring(0, i)) && loop(s.substring(i))) {
                    cache.set(s, true);
                    return true;
                }
            }
        }  
        cache.set(s, false); 
        return false;
    }
    return loop(s);
};

console.assert( wordBreak("leetcode", new Set(["leet", "code"])));

console.log('happy end');


